이진 탐색 트리

작성자

익명

작성일

2026.06.13

조회수

버전

이진 탐색 트리 BST 자료구조 알고리즘 시간 복잡도 균형 잡힌 트리 Python 중위 순회 검색 삽입

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(Binary Search Tree, BST)는 각 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 서브트리의 모든 노드 값이 현재 노드보다 작고 오른쪽 서브트리의 모든 노드 값이 현재 노드보다 큰 순서 속성을 만족하는 이진 트리의 일종입니다.

이러한 구조적 규칙 덕분에 BST는 특정 값을 찾을 때 불필요한 탐색 경로를 제거할 수 있는 효율성을 가지며, 데이터의 빠른 검색, 삽입, 삭제를 가능하게 하는 계층적 자료구조입니다.

이진 탐색 트리의 개요와 기본 개념

이진 탐색 트리(Binary Search Tree, BST)는 일반적인 이진 트리가 단순히 계층적 구조만을 가지는 반면, 이진 탐색 속성(Binary Search Property)이라는 엄격한 규칙을 따릅니다. 이 규칙에 따라 왼쪽 서브트리(Subtree)에 있는 모든 노드의 값은 현재 노드의 값보다 작고, 오른쪽 서브트리에 있는 모든 노드의 값은 현재 노드의 값보다 커야 합니다.

BST를 이해하기 위해 다음과 같은 핵심 용 정의할 수 있습니다. * 노드(Node): 트리의 기본 구성 요소로, 데이터를 저장하고 자식 노드에 대한 참조(포인터)를 포함합니다. * 루트(Root): 트리의 최상단에 위치한 노드로, 부모 노드가 없습니다. 모든 노드는 루트에서 시작하여 도달할 수 있습니다. * 부모(Parent)와 자식(Child): 한 노드에서 다른 노드로 가는 연결 관계에서, 상위 노드를 부모, 하위 노드를 자식이라고 합니다. * 리프(Leaf) 노드: 자식 노드가 하나도 없는 노드로, 트리의 끝부분에 위치합니다.

구조적 특징과 동작 원리

BST의 동작 원리는 재귀적(Recursive) 또는 반복적(Iterative) 알고리즘을 통해 구현됩니다.

데이터 삽입(Insertion) 새로운 값을 삽입할 때는 루트부터 시작하여 현재 노드의 값과 비교합니다. 삽입할 값이 작으면 왼쪽 자식으로, 크면 오른쪽 자식으로 이동합니다. 이 과정을 리프 노드에 도달할 때까지 반복하며, 빈 공간에 새 노드를 연결합니다.

데이터 검색(Searching) 검색 과정도 삽입과 유사합니다. 찾고자 하는 값이 현재 노드의 값과 일치하면 탐색을 종료합니다. 만약 찾는 값이 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 이동하여 재귀적으로 탐색을 계속합니다.

최소/최대값 찾기 BST의 구조적 특성상, 최소값은 가장 왼쪽 끝까지 내려간 노드에서, 최대값은 가장 오른쪽 끝까지 내려간 노드에서 찾을 수 있습니다. 이는 각각 $O(h)$의 시간 복잡도를 가지며, 여기서 $h$는 트리의 높이입니다.

주요 연산과 알고리즘 구현

BST의 가장 복잡한 연산 중 하나는 삭제(Deletion)입니다. 삭제 대상 노드의 자식 노드 개수에 따라 세 가지 경우로 나뉩니다.

리프 노드인 경우: 단순히 해당 노드를 트리에서 제거하면 됩니다.
자식이 하나인 경우: 해당 노드를 제거하고, 남은 자식 노드를 삭제된 노드의 부모가 직접 참조하도록 연결을 재구성합니다.
두 개의 자식을 가진 경우: 이 경우 단순히 노드를 제거하면 트리의 순서 속성이 깨질 수 있습니다. 따라서 후계자(Successor)를 찾아 교체합니다. 일반적으로 '중위 순회(In-order Traversal)'상에서 다음으로 큰 값인 '오른쪽 서브트리의 최소값 노드'를 후계자로 선택합니다. 중위 순회 시 현재 노드의 다음으로 방문되는 노드이므로, 트리의 정렬 순서를 유지할 수 있습니다. 후계자의 값을 삭제 대상 노드에 복사한 후, 후계자 노드 자체는 리프 노드이거나 자식이 하나인 노드이므로 앞서 설명한 1 또는 2번 방식으로 제거합니다.

중위 순회(In-order Traversal) 중위 순회는 '왼쪽 서브트리 방문 -> 현재 노드 방문 -> 오른쪽 서브트리 방문'의 순서로 트리를 순회하는 방법입니다. BST에 중위 순회를 적용하면 노드들의 값이 오름차순으로 정렬된 순서로 출력됩니다. 이는 BST가 정렬된 집합을 구현하는 데 유용한 이유입니다.

코드 예제 (Python 기반 삽입 및 검색)

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def insert(root, key):
    # 본 예제에서는 중복 키를 왼쪽 서브트리에 삽입하는 방식으로 구현되었습니다.
    if root is None:
        return Node(key)
    if root.val < key:
        root.right = insert(root.right, key)
    else:
        root.left = insert(root.left, key)
    return root

def search(root, key):
    if root is None or root.val == key:
        return root
    if key > root.val:
        return search(root.right, key)
    return search(root.left, key)

시간 복잡도 분석과 균형 문제

BST의 성능은 트리의 높이 $h$에 크게 의존합니다.

평균 경우: 노드가 균등하게 분포되어 있을 때, 트리의 높이는 $h \approx \log_2 n$이 됩니다. 따라서 검색, 삽입, 삭제의 시간 복잡도는 모두 $O(\log n)$으로 매우 효율적입니다.
최악 경우: 데이터가 이미 정렬된 순서(예: 1, 2, 3, 4, 5)로 삽입되면, 트리가 한쪽으로 치우친 편향 트리(Skewed Tree)가 됩니다. 이 경우 트리의 높이가 $n$이 되어 시간 복잡도가 $O(n)$으로 떨어지며, 이는 단순 연결 리스트와 동일한 성능을 보입니다.

이러한 한계를 극복하기 위해 균형 잡힌 트리(Balanced Tree)가 개발되었습니다. AVL Tree나 Red-Black Tree와 같은 균형 잡힌 이진 탐색 트리는 삽입 및 삭제 연산 후 트리의 균형을 자동으로 조정하여 높이를 항상 $O(\log n)$으로 유지합니다.

일반 BST vs 균형 잡힌 BST 성능 비교

연산	일반 BST (평균)	일반 BST (최악)	균형 잡힌 BST (AVL/Red-Black)
검색 (Search)	$O(\log n)$	$O(n)$	$O(\log n)$
삽입 (Insert)	$O(\log n)$	$O(n)$	$O(\log n)$
삭제 (Delete)	$O(\log n)$	$O(n)$	$O(\log n)$
최소/최대값	$O(\log n)$	$O(n)$	$O(\log n)$
공간 복잡도	$O(n)$	$O(n)$	$O(n)$

실제 응용 사례와 관련 자료구조

BST는 다양한 분야에서 핵심 자료구조로 활용됩니다.

데이터베이스 인덱싱: 관계형 데이터베이스에서 인덱스는 주로 B-Tree(이진 트리의 확장형)를 사용하지만, 그 기본 원리는 BST의 정렬된 탐색 개념에서 유래했습니다.
자동 완성 시스템: Trie(트리)와 유사하게 사전형 데이터를 저장하고 접두사 기반 검색을 수행하는 데 활용됩니다.
정렬된 집합 구현: C++의 std::set, Java의 TreeMap 등은 내부적으로 Red-Black Tree를 사용하여 정렬된 상태의 데이터 관리와 빠른 조회를 제공합니다.

관련 자료구조와의 비교 * AVL Tree vs Red-Black Tree: AVL Tree는 균형 유지가 더 엄격하여 검색 속도가 빠르지만, 삽입/삭제 시 회전(Rotation) 연산이 빈번하게 발생하여 수정 속도가 느릴 수 있습니다. 반면 Red-Black Tree는 균형 조건이 다소 느슨하여 삽입/삭제가 빈번한 환경에서 더 나은 성능을 보입니다. * 해시 테이블(Hash Table)과의 비교: 해시 테이블은 평균 $O(1)$의 검색 속도를 제공하지만, 최악의 경우 $O(n)$이 될 수 있으며 정렬된 순서 탐색이 불가능합니다. BST는 정렬된 순서 탐색이 가능하고 최악의 경우를 방지하기 위해 균형 알고리즘을 적용할 수 있다는 점에서 장점이 있습니다.

따라서 정렬된 데이터 처리가 필요하거나 범위 검색(Range Query)이 빈번한 경우 BST 기반 자료구조가, 단순 키-값 매핑이 주된 목적이라면 해시 테이블이 더 적합할 수 있습니다.

📝 마크다운 원본

이 문서의 마크다운 원본 내용입니다.

# 이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(Binary Search Tree, BST)는 각 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 서브트리의 모든 노드 값이 현재 노드보다 작고 오른쪽 서브트리의 모든 노드 값이 현재 노드보다 큰 순서 속성을 만족하는 이진 트리의 일종입니다.

이러한 구조적 규칙 덕분에 BST는 특정 값을 찾을 때 불필요한 탐색 경로를 제거할 수 있는 효율성을 가지며, 데이터의 빠른 검색, 삽입, 삭제를 가능하게 하는 계층적 자료구조입니다.

## 이진 탐색 트리의 개요와 기본 개념

이진 탐색 트리(Binary Search Tree, BST)는 일반적인 이진 트리가 단순히 계층적 구조만을 가지는 반면, **이진 탐색 속성(Binary Search Property)**이라는 엄격한 규칙을 따릅니다. 이 규칙에 따라 왼쪽 서브트리(Subtree)에 있는 모든 노드의 값은 현재 노드의 값보다 작고, 오른쪽 서브트리에 있는 모든 노드의 값은 현재 노드의 값보다 커야 합니다.

BST를 이해하기 위해 다음과 같은 핵심 용 정의할 수 있습니다.
*   **노드(Node)**: 트리의 기본 구성 요소로, 데이터를 저장하고 자식 노드에 대한 참조(포인터)를 포함합니다.
*   **루트(Root)**: 트리의 최상단에 위치한 노드로, 부모 노드가 없습니다. 모든 노드는 루트에서 시작하여 도달할 수 있습니다.
*   **부모(Parent)와 자식(Child)**: 한 노드에서 다른 노드로 가는 연결 관계에서, 상위 노드를 부모, 하위 노드를 자식이라고 합니다.
*   **리프(Leaf) 노드**: 자식 노드가 하나도 없는 노드로, 트리의 끝부분에 위치합니다.

## 구조적 특징과 동작 원리

BST의 동작 원리는 재귀적(Recursive) 또는 반복적(Iterative) 알고리즘을 통해 구현됩니다.

**데이터 삽입(Insertion)**
새로운 값을 삽입할 때는 루트부터 시작하여 현재 노드의 값과 비교합니다. 삽입할 값이 작으면 왼쪽 자식으로, 크면 오른쪽 자식으로 이동합니다. 이 과정을 리프 노드에 도달할 때까지 반복하며, 빈 공간에 새 노드를 연결합니다.

**데이터 검색(Searching)**
검색 과정도 삽입과 유사합니다. 찾고자 하는 값이 현재 노드의 값과 일치하면 탐색을 종료합니다. 만약 찾는 값이 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 이동하여 재귀적으로 탐색을 계속합니다.

**최소/최대값 찾기**
BST의 구조적 특성상, **최소값**은 가장 왼쪽 끝까지 내려간 노드에서, **최대값**은 가장 오른쪽 끝까지 내려간 노드에서 찾을 수 있습니다. 이는 각각 $O(h)$의 시간 복잡도를 가지며, 여기서 $h$는 트리의 높이입니다.

## 주요 연산과 알고리즘 구현

BST의 가장 복잡한 연산 중 하나는 **삭제(Deletion)**입니다. 삭제 대상 노드의 자식 노드 개수에 따라 세 가지 경우로 나뉩니다.

1.  **리프 노드인 경우**: 단순히 해당 노드를 트리에서 제거하면 됩니다.
2.  **자식이 하나인 경우**: 해당 노드를 제거하고, 남은 자식 노드를 삭제된 노드의 부모가 직접 참조하도록 연결을 재구성합니다.
3.  **두 개의 자식을 가진 경우**: 이 경우 단순히 노드를 제거하면 트리의 순서 속성이 깨질 수 있습니다. 따라서 **후계자(Successor)**를 찾아 교체합니다. 일반적으로 '중위 순회(In-order Traversal)'상에서 다음으로 큰 값인 '오른쪽 서브트리의 최소값 노드'를 후계자로 선택합니다. 중위 순회 시 현재 노드의 다음으로 방문되는 노드이므로, 트리의 정렬 순서를 유지할 수 있습니다. 후계자의 값을 삭제 대상 노드에 복사한 후, 후계자 노드 자체는 리프 노드이거나 자식이 하나인 노드이므로 앞서 설명한 1 또는 2번 방식으로 제거합니다.

**중위 순회(In-order Traversal)**
중위 순회는 '왼쪽 서브트리 방문 -> 현재 노드 방문 -> 오른쪽 서브트리 방문'의 순서로 트리를 순회하는 방법입니다. BST에 중위 순회를 적용하면 노드들의 값이 오름차순으로 정렬된 순서로 출력됩니다. 이는 BST가 정렬된 집합을 구현하는 데 유용한 이유입니다.

### 코드 예제 (Python 기반 삽입 및 검색)

```python
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def insert(root, key):
    # 본 예제에서는 중복 키를 왼쪽 서브트리에 삽입하는 방식으로 구현되었습니다.
    if root is None:
        return Node(key)
    if root.val < key:
        root.right = insert(root.right, key)
    else:
        root.left = insert(root.left, key)
    return root

def search(root, key):
    if root is None or root.val == key:
        return root
    if key > root.val:
        return search(root.right, key)
    return search(root.left, key)
```

## 시간 복잡도 분석과 균형 문제

BST의 성능은 트리의 높이 $h$에 크게 의존합니다.

*   **평균 경우**: 노드가 균등하게 분포되어 있을 때, 트리의 높이는 $h \approx \log_2 n$이 됩니다. 따라서 검색, 삽입, 삭제의 시간 복잡도는 모두 **$O(\log n)$**으로 매우 효율적입니다.
*   **최악 경우**: 데이터가 이미 정렬된 순서(예: 1, 2, 3, 4, 5)로 삽입되면, 트리가 한쪽으로 치우친 편향 트리(Skewed Tree)가 됩니다. 이 경우 트리의 높이가 $n$이 되어 시간 복잡도가 **$O(n)$**으로 떨어지며, 이는 단순 연결 리스트와 동일한 성능을 보입니다.

이러한 한계를 극복하기 위해 **균형 잡힌 트리(Balanced Tree)**가 개발되었습니다. AVL Tree나 Red-Black Tree와 같은 균형 잡힌 이진 탐색 트리는 삽입 및 삭제 연산 후 트리의 균형을 자동으로 조정하여 높이를 항상 $O(\log n)$으로 유지합니다.

### 일반 BST vs 균형 잡힌 BST 성능 비교

| 연산 | 일반 BST (평균) | 일반 BST (최악) | 균형 잡힌 BST (AVL/Red-Black) |
| :--- | :---: | :---: | :---: |
| **검색 (Search)** | $O(\log n)$ | $O(n)$ | $O(\log n)$ |
| **삽입 (Insert)** | $O(\log n)$ | $O(n)$ | $O(\log n)$ |
| **삭제 (Delete)** | $O(\log n)$ | $O(n)$ | $O(\log n)$ |
| **최소/최대값** | $O(\log n)$ | $O(n)$ | $O(\log n)$ |
| **공간 복잡도** | $O(n)$ | $O(n)$ | $O(n)$ |

## 실제 응용 사례와 관련 자료구조

BST는 다양한 분야에서 핵심 자료구조로 활용됩니다.

1.  **데이터베이스 인덱싱**: 관계형 데이터베이스에서 인덱스는 주로 B-Tree(이진 트리의 확장형)를 사용하지만, 그 기본 원리는 BST의 정렬된 탐색 개념에서 유래했습니다.
2.  **자동 완성 시스템**: Trie(트리)와 유사하게 사전형 데이터를 저장하고 접두사 기반 검색을 수행하는 데 활용됩니다.
3.  **정렬된 집합 구현**: C++의 `std::set`, Java의 `TreeMap` 등은 내부적으로 Red-Black Tree를 사용하여 정렬된 상태의 데이터 관리와 빠른 조회를 제공합니다.

**관련 자료구조와의 비교**
*   **AVL Tree vs Red-Black Tree**: AVL Tree는 균형 유지가 더 엄격하여 검색 속도가 빠르지만, 삽입/삭제 시 회전(Rotation) 연산이 빈번하게 발생하여 수정 속도가 느릴 수 있습니다. 반면 Red-Black Tree는 균형 조건이 다소 느슨하여 삽입/삭제가 빈번한 환경에서 더 나은 성능을 보입니다.
*   **해시 테이블(Hash Table)과의 비교**: 해시 테이블은 평균 $O(1)$의 검색 속도를 제공하지만, 최악의 경우 $O(n)$이 될 수 있으며 정렬된 순서 탐색이 불가능합니다. BST는 정렬된 순서 탐색이 가능하고 최악의 경우를 방지하기 위해 균형 알고리즘을 적용할 수 있다는 점에서 장점이 있습니다.

따라서 정렬된 데이터 처리가 필요하거나 범위 검색(Range Query)이 빈번한 경우 BST 기반 자료구조가, 단순 키-값 매핑이 주된 목적이라면 해시 테이블이 더 적합할 수 있습니다.

AI 생성 콘텐츠 안내

이 문서는 AI 모델(qwen/qwen3.6-35b-a3b)에 의해 생성된 콘텐츠입니다.

주의사항: AI가 생성한 내용은 부정확하거나 편향된 정보를 포함할 수 있습니다. 중요한 결정을 내리기 전에 반드시 신뢰할 수 있는 출처를 통해 정보를 확인하시기 바랍니다.

위키너와나